1. Field of the Invention
This invention relates to computer systems and, more particularly, to methods and apparatus for addressing information in caches used by computer system.
2. History of the Prior Art
Caches are used in computer systems to speed the overall operation of the system. The theory of a cache is that a system attains a higher speed by using a small portion of very fast random access memory (RAM) as a cache along with a larger amount of slower main memory RAM. If data and instructions are called from main memory and placed in cache memory as they are required by the program, and if the system looks first to the cache memory to see if the information required is available there, then the system will usually find the information desired in the cache memory and will, consequently, operate at a speed as though it were made up mostly of high speed cache memory. This usually happens because, statistically, information in any particular portion of a process which has just been used is more likely to be required immediately than is other information which has not been recently used.
There have been many forms of caching systems devised by the prior art. One way to design a cache memory used in a demand paged virtual memory system is to give the cache memory the same size as one of the main memory pages. When, in such a system, information is taken from main memory and placed in a cache, it may be stored in the same line of the cache memory as the line of the page from which it was accessed in main memory. The information may be stored in the cache memory along with its page address in main memory. Each line of the cache memory in such a system may come from any particular page of main memory so that lines lying adjacent each other in cache memory may have entirely different page addresses. The page address is stored as part of a tag field, a series of high order bits of the address which in addition to the page designation include protection and control information such as whether the information is read or write protected and whether the information is valid. In a particular system, such a tag field may require approximately sixteen bits to represent the tag information.
Then a system capable of accessing any line in a cache memory may determine whether the required information is in the cache memory (whether there is a hit) by looking to the particular line designated in the address sought to see whether the correct page number is stored in the tag field. If the virtual page address at the desired line in the cache memory matches the desired virtual page address, then there is a hit; and the information in the cache memory is used without the necessity of going to main memory. If the information is not present in cache memory, then the system must delay, go to the main memory, replace the particular line in the cache memory, and then operate on the information.
Since the hit rate usually runs as high as ninety-five percent, some computer systems using pipelining procedures go ahead and process the information found at the addressed line of the cache without waiting for the tag comparison to determine if the information has the correct virtual page address in order to eliminate in most cases the time taken for a tag comparison. While the information is being processed, the tag comparison is conducted; and, if there is a miss, the incorrect information is simply dumped. Overall, this is faster than conducting the tag comparison first for each address in the cache.
Of course, such a system does have disadvantages. When there is miss in the cache memory, several clock times may have passed before main memory is accessed for the missed information. Moreover, the pipelining system must contain sufficient additional pipeline stages to allow incorrect information to overflow and be dumped. Moreover, the system uses quite a bit of address space in the cache memory to provide the space necessary for the tags to designate pages of main memory and control and protection information.